// 版权所有2009 Go作者。保留所有权利。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

package flate

import (
	"math"
	"math/bits"
	"sort"
)

// hcode是一种具有位代码和位长度的哈夫曼码。
type hcode struct {
	code, len uint16
}

type huffmanEncoder struct {
	codes     []hcode
	freqcache []literalNode
	bitCount  [17]int32
	lns       byLiteral // 在generate中存储以避免重复分配
	lfs       byFreq    // 在generate中存储以避免重复分配
}

type literalNode struct {
	literal uint16
	freq    int32
}

// levelInfo描述给定深度下构造的树的状态。我们的水平。为了更好地打印
type levelInfo struct {
	level int32

	// 此级别最后一个节点的频率
	lastFreq int32

	// 要添加到此级别的下一个字符的频率
	nextCharFreq int32

	// 要添加到此级别的下一对字符的频率（从下面的级别开始）。
	// 仅当下一个较低级别的“需要”值为0时有效。
	nextPairFreq int32

	// 在移动
	// 到下一个级别之前，此级别剩余要生成的链数
	needed int32
}

// set设置一个hcode的代码和长度。
func (h *hcode) set(code uint16, length uint16) {
	h.len = length
	h.code = code
}

func maxNode() literalNode { return literalNode{math.MaxUint16, math.MaxInt32} }

func newHuffmanEncoder(size int) *huffmanEncoder {
	return &huffmanEncoder{codes: make([]hcode, size)}
}

// 生成与固定文字表
func generateFixedLiteralEncoding() *huffmanEncoder {
	h := newHuffmanEncoder(maxNumLit)
	codes := h.codes
	var ch uint16
	for ch = 0; ch < maxNumLit; ch++ {
		var bits uint16
		var size uint16
		switch {
		case ch < 144:
			// 大小8，00011000.相对应的HuffmanCode。。10111111 
			bits = ch + 48
			size = 8
			break
		case ch < 256:
			// 9号，110010000。。111111111 
			bits = ch + 400 - 144
			size = 9
			break
		case ch < 280:
			// 尺寸700000。。0010111 
			bits = ch - 256
			size = 7
			break
		default:
			// 8号，11000000。。11000111 
			bits = ch + 192 - 280
			size = 8
		}
		codes[ch] = hcode{code: reverseBits(bits, byte(size)), len: size}
	}
	return h
}

func generateFixedOffsetEncoding() *huffmanEncoder {
	h := newHuffmanEncoder(30)
	codes := h.codes
	for ch := range codes {
		codes[ch] = hcode{code: reverseBits(uint16(ch), 5), len: 5}
	}
	return h
}

var fixedLiteralEncoding *huffmanEncoder = generateFixedLiteralEncoding()
var fixedOffsetEncoding *huffmanEncoder = generateFixedOffsetEncoding()

func (h *huffmanEncoder) bitLength(freq []int32) int {
	var total int
	for i, f := range freq {
		if f != 0 {
			total += int(f) * int(h.codes[i].len)
		}
	}
	return total
}

const maxBitsLimit = 16

// 返回在哈夫曼编码
// 
// 中分配给每个位大小的文本数，此方法仅在列表时调用。长度>=3 
// 0、1和2文本的大小写由特殊大小写代码处理。
// 
// 列出非零频率的文本数组
// 及其相关频率。该数组按增加
// 频率的顺序排列，最后一个元素是一个特殊元素，其频率为
// MaxInt32 
// maxBits应用于编码任何文字的最大位数。
// 必须小于16。
// 返回一个整数数组，其中数组[i]表示应以i位编码的文本数
// 。
func (h *huffmanEncoder) bitCounts(list []literalNode, maxBits int32) []int32 {
	if maxBits >= maxBitsLimit {
		panic("flate: maxBits too large")
	}
	n := int32(len(list))
	list = list[0 : n+1]
	list[n] = maxNode()

	// 无论如何，树的深度都不能超过n-1。这个
	// 在一些小案例中节省了一点工作
	if maxBits > n-1 {
		maxBits = n - 1
	}

	// 创建关于每个级别的信息。
	// 一个伪造的“0级”，其唯一目的是使
	// 1级。上一篇。需要==0。这就是level1。nextPairFreq 
	// 是一个永远不会被选择的合法值。
	var levels [maxBitsLimit]levelInfo
	// leafCounts[i]计算级别i最右侧节点的祖先在左侧的文本数
	// 。
	// leafCounts[i][j]是级别j祖先在左侧的文本数
	// 。
	var leafCounts [maxBitsLimit][maxBitsLimit]int32

	for level := int32(1); level <= maxBits; level++ {
		// 对于每个级别，前两项是前两个字符。
		// 我们初始化这些级别，就好像我们已经解决了这个问题一样。
		levels[level] = levelInfo{
			level:        level,
			lastFreq:     list[1].freq,
			nextCharFreq: list[2].freq,
			nextPairFreq: list[0].freq + list[1].freq,
		}
		leafCounts[level][level] = 2
		if level == 1 {
			levels[level].nextPairFreq = math.MaxInt32
		}
	}

	// 我们总共需要2*n-2个顶级项目，并且已经生成了2个。
	levels[maxBits].needed = 2*n - 4

	level := maxBits
	for {
		l := &levels[level]
		if l.nextPairFreq == math.MaxInt32 && l.nextCharFreq == math.MaxInt32 {
			// 我们的叶子和鞋子都用完了。
			// 结束此级别的所有计算。
			// 为了确保我们永远不会回到这个级别或任何更低的级别，
			// 将nextPairFreq设置为不可能的大。
			l.needed = 0
			levels[level+1].nextPairFreq = math.MaxInt32
			level++
			continue
		}

		prevFreq := l.lastFreq
		if l.nextCharFreq < l.nextPairFreq {
			// 此行的下一项是叶节点。
			n := leafCounts[level][level] + 1
			l.lastFreq = l.nextCharFreq
			// 较低的叶数与前一个节点相同。
			leafCounts[level][level] = n
			l.nextCharFreq = list[n].freq
		} else {
			// 此行的下一项是上一行的一对。
			// nextPairFreq在我们生成两个
			// 以下级别的更多值之前无效
			l.lastFreq = l.nextPairFreq
			// 从较低级别获取叶计数，但计数[level]保持不变。
			copy(leafCounts[level][:level], leafCounts[level-1][:level])
			levels[l.level-1].needed = 2
		}

		if l.needed--; l.needed == 0 {
			// 我们已经为这个级别做了我们需要做的一切。
			// 继续向上计算一级。用我们刚刚在
			// 。
			// 这个级别上计算的两个节点的总和填写该级别的nextPairFreq 
			if l.level == maxBits {
				// 全部完成！
				break
			}
			levels[l.level+1].nextPairFreq = prevFreq + l.lastFreq
			level++
		} else {
			// 如果我们从下面偷东西，暂时下楼补充。
			for levels[level-1].needed > 0 {
				level--
			}
		}
	}

	// 如果最后顶层为空或没有使用所有的叶子，则有些事情是错误的。
	if leafCounts[maxBits][maxBits] != n {
		panic("leafCounts[maxBits][maxBits] != n")
	}

	bitCount := h.bitCount[:maxBits+1]
	bits := 1
	counts := &leafCounts[maxBits]
	for level := maxBits; level > 0; level-- {
		// 链。leafCount给出至少需要“位”
		// 位进行编码的文本数。
		bitCount[bits] = counts[level] - counts[level-1]
		bits++
	}
	return bitCount
}

// 查看叶子，并按照RFC 1951 3.2.2中的
// 指定给它们一个位计数和一个编码。。list[len（list）-bits]
func (h *huffmanEncoder) assignEncodingAndSize(bitCount []int32, list []literalNode) {
	code := uint16(0)
	for n, bits := range bitCount {
		code <<= 1
		if n == 0 || bits == 0 {
			continue
		}
		// 使用“bits”位进行编码，并获得值
		// code，code+1。。。。代码值为
		// 按文字顺序分配（不是频率顺序）。
		chunk := list[len(list)-int(bits):]

		h.lns.sort(chunk)
		for _, node := range chunk {
			h.codes[node.literal] = hcode{code: reverseBits(code, uint8(n)), len: uint16(n)}
			code++
		}
		list = list[0 : len(list)-int(bits)]
	}
}

// 将此哈夫曼代码对象更新为指定频率计数的最小代码。
// 
// freq一组频率，其中frequency[i]给出文字i的频率。
// maxBits任何文字使用的最大位数。
func (h *huffmanEncoder) generate(freq []int32, maxBits int32) {
	if h.freqcache == nil {
		// 分配一个具有尽可能长的频率表的可重用缓冲区。
		// 可能的长度为codegenCodeCount、offsetCodeCount和maxNumLit。
		// 其中最大的是maxNumLit，所以我们为这种情况分配了资源。
		h.freqcache = make([]literalNode, maxNumLit+1)
	}
	list := h.freqcache[:len(freq)+1]
	// 非零字面值的数量
	count := 0
	// 将列表设置为所有非零字面值及其频率的集合
	for i, f := range freq {
		if f != 0 {
			list[count] = literalNode{uint16(i), f}
			count++
		} else {
			list[count] = literalNode{}
			h.codes[i].len = 0
		}
	}
	list[len(freq)] = literalNode{}

	list = list[:count]
	if count <= 2 {
		// 处理这里的小案例，因为它们不适合一般案例代码。对于
		// 两个或更少的文本，所有内容的位长度都为1。
		for i, node := range list {
			// /“list”按字面值递增的顺序排列。
			h.codes[node.literal].set(uint16(i), 1)
		}
		return
	}
	h.lfs.sort(list)

	// 获取每个位计数的文本数
	bitCount := h.bitCounts(list, maxBits)
	// 并执行赋值
	h.assignEncodingAndSize(bitCount, list)
}

type byLiteral []literalNode

func (s *byLiteral) sort(a []literalNode) {
	*s = byLiteral(a)
	sort.Sort(s)
}

func (s byLiteral) Len() int { return len(s) }

func (s byLiteral) Less(i, j int) bool {
	return s[i].literal < s[j].literal
}

func (s byLiteral) Swap(i, j int) { s[i], s[j] = s[j], s[i] }

type byFreq []literalNode

func (s *byFreq) sort(a []literalNode) {
	*s = byFreq(a)
	sort.Sort(s)
}

func (s byFreq) Len() int { return len(s) }

func (s byFreq) Less(i, j int) bool {
	if s[i].freq == s[j].freq {
		return s[i].literal < s[j].literal
	}
	return s[i].freq < s[j].freq
}

func (s byFreq) Swap(i, j int) { s[i], s[j] = s[j], s[i] }

func reverseBits(number uint16, bitLength byte) uint16 {
	return bits.Reverse16(number << (16 - bitLength))
}
